package com.example.jianzhioffer;

/**
 * Created by Quincy on 2018/9/23.
 * 无序数组找中位数
 */
public class UnSortedMedium {
/**
 * 如果数组长度是奇数，中位数是排序后的第(n+1)/2个元素；若是偶数，中位数是排序后第n/2个元素。

 * 思路1：

 * 1.1 将前(n+1)/2个元素调整为一个最小堆；
 * 1.2 对后续每一个元素和堆顶比较，如果小于等于堆顶，丢弃之，去下一个元素。
 * 如果大于堆顶，用该元素取代堆顶，调整堆，去下一个元素重复1.2步
 * 1.3 当遍历完所有元素之后，堆顶为中位数

 * 思路2：
 可以扩展为从无序数组中查找第k大的元素。

 利用快速排序的partition函数，任意挑一个元素，以该元素key，划分数组为两部分，key左边元素小于等于key，
 右边元素大于等于key。在第一次partition后，如果左侧元素个数<k - 1，则在右侧子序列中递归查找；如果左侧元素个数=k-1，
 则第k大元素即在分点处；如果左侧元素个数>k - 1,则递归地在左侧序列中继续查找

 * */
    public static void swap(int[] a, int i, int j){
        int temp = a[i];
        a[i] =  a[j];
        a[j] = temp;
    }

    public static int partition(int[] arr, int low, int high){
        int pivot = arr[low];
        int i= low, j = high;
        while(i<=j){
            while(i<=j && arr[i]<=pivot)i++;
            while(i<=j && arr[j]>=pivot)j--;
            swap(arr,i,j);
        }
        swap(arr,low,j);
        return j;
    }
    //第k大的数，如果数组长度奇数，则k=(1+n)/2, 否则k=n/2
    public static int findMedian(int[] arr, int k, int low, int high){
        if(k >high -low +1) return -1;
        int pos = partition(arr,low, high);
        if(pos - low < k -1){
            return findMedian(arr, k-pos-1, pos+1, high);
        }else if(pos - low == k-1){
            return arr[pos];
        }else {
            return findMedian(arr, k, low, pos-1);
        }
    }


    public static void main(String[] args) {
        int[] arr= {3,5,2,3,5,9,1,2,11,12,13};
        int res = 0;
        if(arr.length%2 ==1){
            res = findMedian(arr, (arr.length+1)/2, 0, arr.length-1);
        }else{
            res = findMedian(arr, arr.length/2, 0, arr.length-1);
        }
        System.out.println(res);
    }


}
